import java.util.HashMap;

public class LRUCache {

    int usedSized;
    HashMap<Integer,LRUCacheNode> hashMap;
    int capacity;
    final int DEFAULT_CAPACITY = 3;//默认容量

    static class LRUCacheNode {
        int key;
        int val;
        LRUCacheNode prev;
        LRUCacheNode next;

        public LRUCacheNode() {}

        public  LRUCacheNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    LRUCacheNode head;
    LRUCacheNode tail;

    public LRUCache() {
        hashMap = new HashMap<>();
        head = new LRUCacheNode();
        tail = new LRUCacheNode();
        head.next = tail;
        tail.prev = head;
        capacity = DEFAULT_CAPACITY;
    }

    public LRUCache(int initCapacity) {
        hashMap = new HashMap<>();
        head = new LRUCacheNode();
        tail = new LRUCacheNode();
        head.next = tail;
        tail.prev = head;
        capacity = initCapacity;
    }

    //插入结点
    public void put(int key, int val) {

        //如果存在 node 直接更新
        LRUCacheNode find = hashMap.get(key);
        if(find != null) {
            find.prev.next = find.next;
            find.next.prev = find.prev;
            insertToTail(find);
            find.val = val;
            return;
        }

        LRUCacheNode node = new LRUCacheNode(key,val);

        if(usedSized < capacity) {
            insertToTail(node);
            usedSized++;
        } else {
            //删除
            LRUCacheNode del = head.next;
            removeNode(del);
            hashMap.remove(del);

            //插入
            insertToTail(node);
        }
    }

    private void insertToTail(LRUCacheNode node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    private void removeNode(LRUCacheNode node) {
        head.next = node.next;
        node.next.prev = node.prev;
    }

    //查找
    public int get(int key) {
        LRUCacheNode node = hashMap.get(key);
        if(node == null) { //不存在直接返回 -1
            return -1;
        }
        return node.val;
    }
}
